Climbing Stairs

LeetCode 70 | Difficulty: Easy

Easy

Problem Description

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

- `1 <= n <= 45`

Topics: Math, Dynamic Programming, Memoization

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

Mathematical

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

---

Solutions

Solution 1: C# (Best: 40 ms)

Metric	Value
Runtime	40 ms
Memory	14 MB
Date	2019-12-15

Solution

public class Solution {
    public int ClimbStairs(int n)
{
    Dictionary<int, int> mem = new Dictionary<int, int>();
    mem.Add(0, 0);
    mem.Add(1, 1);
    mem.Add(2,2);   
    return ClimbStairs(n, mem); 
}
private int ClimbStairs(int n, Dictionary<int, int> mem)
{
    if(mem.ContainsKey(n)) return mem[n];
    var result = ClimbStairs(n-1, mem)+ClimbStairs(n-2,mem);
    mem.Add(n,result);
    return result;
}
}

📜 1 more C# submission(s)

Submission (2017-10-29) — 62 ms, N/A

public class Solution {
    public int ClimbStairs(int n)
{
    Dictionary<int, int> mem = new Dictionary<int, int>();
    mem.Add(0, 0);
    mem.Add(1, 1);
    mem.Add(2,2);   
    return ClimbStairs(n, mem); 
}
private int ClimbStairs(int n, Dictionary<int, int> mem)
{
    if(mem.ContainsKey(n)) return mem[n];
    var result = ClimbStairs(n-1, mem)+ClimbStairs(n-2,mem);
    mem.Add(n,result);
    return result;
}
}

---

Complexity Analysis

Approach	Time	Space
Dynamic Programming	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.
• LeetCode provides 1 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: To reach nth step, what could have been your previous steps? (Think about the step sizes)